Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

• 1,2,3 → 1,3,2
  
• 3,2,1 → 1,2,3
  
• 1,1,5 → 1,5,1

题目大意：给定一个数组，代表一个排列，给出该排列的下一个排列（字典序）。要求空间复杂度O(1)

题目难度：Medium

/**
 * Created by gzdaijie on 16/5/18
 * 问题的关键是找到使得数字更改最小的节点
 * 假设nums长度为n,应当替换的位置为p,可以证明p + 1 -> n降序排列的,且nums[p] < nums[p+1]
 * 否则可以找到 q（q>p）,使得q + 1->n降序排列,且nums[q] < nums[q+1],替换q,对数字影响更小
 * 时间复杂度O(N)
 */
public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 1) return;
        int len = nums.length;
        int k = len - 2;
        // 找到降序排列的最长后缀
        for (; k >=0 && nums[k] >= nums[k + 1] ; k--); /* empty */

        if (k >= 0) {
            // 从后往前,找到恰好比比nums[k]大的数字nums[i],替换nums[k]和nums[i]
            for (int i = len - 1; i > k; i--) {
                if (nums[i] > nums[k]) {
                    int t = nums[i];
                    nums[i] =  nums[k];
                    nums[k] = t;
                    break;
                }
            }
        }
        // 翻转k+1 -> len - 1（降序排列的数,翻转之后即可以保证最小）
        // 这里有一个特殊情况,k若等于-1,说明整个序列是降序的,那么相当于翻转全部
        reverse(nums, k + 1, len - 1);
    }

    /**
     * 翻转一个数组
     * @param nums 待翻转的数组
     * @param start 开始位置（含）
     * @param end 结束位置（含）
     */
    public void reverse(int[] nums, int start, int end) {
        int mid = (end - start + 1) / 2;
        for (int i = 0; i < mid; i++) {
            int t = nums[start + i];
            nums[start + i] = nums[end - i];
            nums[end - i] = t;
        }
    }
}

参考：下一个排列图解